#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
int B = 1;
int U = 100;
typedef struct Black
{
int Bnum;
int Bfirst;
int Bleng;
int Blast;
}Black;
typedef struct Use
{
char Ufile[8];
int Ufirst;
int Uleng;
int Ulast;
int Uflg;
}Use;
Black black[] = { {0,0,100,99} }; //初始化
Use use[100] = { 0 };
void bubbleSort(Black a[], int m)
//为了实现再次新建文件时提高分配利用率(将空白块按空白个数从小到大排序)
{
for (int i = 0; i <m; i++)
 {
for (int j = 0; j <m - 1; j++)
 {
if (a[j].Bfirst >a[j + 1].Bfirst)
 {
Black temp = a[j];
a[j] =a[j + 1];
a[j + 1] = temp;
 }
 }
 }
}
void PrintBlack()
{
int num = 1;
 cout <<"***当前的空文件目录表"<< endl;
 cout <<"序号\t 首块号\t 空白块个数\t 末块号"<< endl;
for (int i = 0; i < B; i++)
 {
 cout << num <<"\t"<< black[i].Bfirst <<"\t"<< black[i].Bleng <<"\t\t"<<
black[i].Blast << endl;
 num++;
 }
 cout << endl;
}
void PrintUse()
{
 cout <<"***当前的已使用文件目录***"<< endl;
 cout <<"序号\t 首块号\t 空白块个数\t 末块号"<< endl;
for (int i = 0; i < U; i++)
 {
if (use[i].Uflg == 1)
 {
 cout << use[i].Ufile <<"\t"<< use[i].Ufirst <<"\t"<< use[i].Uleng 
<<"\t\t"<< use[i].Ulast << endl;
 }
 }
 cout << endl;
}
void Distribute()
{
 cout <<"输入文件名和块数"<< endl;
char fname[8]; //文件名
int m; //块数
int temp; //记录要插入的首块号（空白区中的）
int t = 1;//为了遍历完空白表的验证非法的输入（块数大于空白区的所有块数）
 scanf("%s", fname);
 cin >> m;
for (int i = 0; i < B; i++)
 {
 t++;
for (int j = 0; j < U; j++)
 {
if (!strcmp(fname, use[j].Ufile))
 {
 cout <<"***此文件名已经存在!请转换文件名***"<< endl;
return;
 }
 }
if (black[i].Bleng >= m)
 {
 temp = black[i].Bfirst;
if (black[i].Bleng == m)//删除空白区
 {
for (int i = 0; i < B - 1; i++)
 {
 black[i].Bfirst = black[i + 1].Bfirst;
 black[i].Bleng = black[i + 1].Bleng;
 black[i].Blast = black[i + 1].Blast;
 }
 B--;
 }
else//修改空白区
 {
 black[i].Bleng -= m;
 black[i].Bfirst += m;
 }
 strcpy(use[U].Ufile, fname);
 use[U].Ufirst = temp;
 use[U].Uleng = m;
 use[U].Ulast = use[U].Ufirst + use[U].Uleng - 1;
 use[U].Uflg = 1;
 U++;
break;
 }
else
 {
if (t == B)
 cout <<"由于 m 块数大于空闲区无法分配"<< endl;
 }
 }
 bubbleSort(black, B);
 PrintBlack();
 PrintUse();
}
void Release()
{
int flag = 0; //标记输入的文件名是否存在
int ufirst; //首块号
int uleng; //文件块数
int ulast; //文件末块
char fname[8];
 cout <<"输入删除的文件的文件名"<< endl;
 scanf("%s", fname);
for (int i = 0; i < U; i++)
 {
int fT = 0;
int Tnum = 0;
int fB = 0;
int Bnum = 0;
if (!strcmp(fname, use[i].Ufile))
 {
 flag = 1;
 ulast = use[i].Ulast;
 ufirst = use[i].Ufirst;
 uleng = use[i].Uleng;
 use[i].Uflg = -1;
for (int j = 0; j < B; j++) //遍历判断上下邻
if ((black[j].Blast + 1) == ufirst)
 {
 fT = 1; //存在上邻
 Tnum = j;
 }
int j = 0;
if ((black[j].Bfirst - 1) == ulast)
 {
 fB = 1; //存在下邻
 Bnum = j;
 }
if (fT && (!fB)) //有上邻，无下邻
 {
 black[Tnum].Bleng += uleng;
 black[Tnum].Blast = ulast;
 }
if (fT && fB)//有上邻，有下邻
 {
 black[Tnum].Bleng += (uleng + black[Bnum].Bleng);
 black[Tnum].Blast = black[Bnum].Blast;
for (Bnum = 0; Bnum < B; Bnum++)
 {
 black[Bnum] = black[Bnum + 1];
 black[Bnum].Bnum = Bnum + 1;
 }
 B--;
 }
if ((!fT) && (!fB)) //无上邻无下邻
 {
 black[B].Bnum = B;
 black[B].Bfirst = ufirst;
 black[B].Bleng = uleng;
 black[B].Blast = ulast;
 B++;
 }
if ((!fT) && fB)
 {
 black[Bnum].Bleng += uleng;
 black[Bnum].Bfirst = ufirst;
 }
 }
 }
if (flag == 0)
 {
 cout <<"***输入文件不存在***"<< endl;
 }
 bubbleSort(black, B);
 PrintBlack();
 PrintUse();
}
int main()
{
 cout <<"***模拟文件存储空白文件目录***"<< endl << endl;
 PrintBlack();
 PrintUse();
int n;
while (1)
 {
 cout <<"************"<< endl;
 cout <<"请按如下输入进行操作(分配:1 释放:2 结束:3)";
 fflush(stdin);
 cin >> n;
 getchar();
 system("cls");
if (n == 1)
 Distribute();
else if (n == 2)
 Release();
else if (n == 3)
{
    system("pause");
return 0;
}
else
 {
 cout <<"重新输入"<< endl;
 }
 }
}